//
// Created by Administrator on 2021/11/9.
// May Saint Diana bless you!
//

#include <vector>
#include <iostream>

using namespace std;

class Solution {
private:
    int target = 0;
    int ans = 0;
    int n = 0;
    vector<int> cur;
public:
    int countMaxOrSubsets(vector<int> &nums) {
        for (const int &x:nums)
            target |= x;
        n = (int) nums.size();
        backtracking(nums, 0);
        return ans;
    }

    void backtracking(vector<int> &nums, int index) {
        if (index == n) {
            check();
            return;
        }
        cur.push_back(nums[index]);
        backtracking(nums, index + 1);
        cur.pop_back();
        backtracking(nums, index + 1);
    }

    void check() {
        int temp = 0;
        for (const int &x:cur) {
            temp |= x;
        }
        if (temp == target) {
            for (const int &x:cur) {
                cout << x << " ";
            }
            cout << endl;
        }
        if (temp == target)
            ++ans;
    }
};

class Solution2 {    // backtracking
public:
    int maxx = 0;
    int ans = 0;

    int countMaxOrSubsets(vector<int> &nums) {
        for (int &i : nums) maxx |= i;
        backtrack(nums, 0, 0, false);
        return ans;
    }

    void backtrack(vector<int> &nums, int tmp, int idx, bool sign) {
        if (tmp == maxx && sign) ++ans;     // 只有本次选中的元素，子集才不会重复
        if (idx == nums.size()) return;   // 搜完就回溯
        backtrack(nums, tmp, idx + 1, false);             // 搜下一个元素，不选中
        backtrack(nums, tmp | nums[idx], idx + 1, true);  // 搜下一个元素，选中
    }
};

int main() {
    vector<int> nums{3, 2, 1, 5};
//    vector<int> nums{2,2,2};
    Solution solution;
    cout << solution.countMaxOrSubsets(nums) << endl;
    return 0;
}